The present invention relates to digital data transmission and, in particular, to error correcting codes.
Continued advances in forward error-correcting codes, such as convolutional codes and trellis codes, have enabled designers of modems, wireless communications systems and other digital communications systems to achieve increased bit rates for a given level of error rate performance. Among the various innovations that have been introduced over the years are so-called turbo codes. At the heart of the turbo code concept is the encoding of input data using more than one encoder combined with an interleaver in such a way that improved performance (as compared to a single encoding) can be achieved using a corresponding number of so-called soft input/soft output decoders which operate iteratively.
An early description of turbo codes appears in C. Berrou, et al, "Near Shannon limit error-correcting coding and decoding: Turbo codes," Proc. 1993 Int. Conf. Communication (Geneva, Switzerland, May 1993), pp. 1064-1070. Berrou et al discloses a so-called parallel-concatenated turbo code. The input data is applied to a first convolutional encoder and an interleaved version of the input data is applied to a second convolutional encoder. The output bits of the two encoders are then mapped into signal points of a two-dimensional (2D) 4-PSK signaling constellation for transmission. Some of the redundant bits generated by the encoders may be subjected to a so-called puncturing prior to the mapping step in order to improve bandwidth efficiency (measured in bits per 2D signal point).
At relatively high error rates, a parallel concatenated turbo code provides excellent coding gain, thereby advantageously reducing the level of received signal-to-noise ratio required in order to realize a desired level of error rate performance. Disadvantageously, however, achieving that excellent coding gain requires an extremely long interleaver. This introduces significant end-to-end delay, or latency, which is undesirable in many applications. Moreover, a parallel-concatenated turbo code exhibits a so-called error floor phenomenon wherein the improvement in coding gain is far less dramatic at lower error rates and, indeed, may be comparable to, or even worse than, that achieved using more conventional encoding and decoding.
Also known in the prior art are so-called serial-concatenated turbo codes, as disclosed, for example, by S. Benedetto, et al, "Serial concatenation of interleaved codes: Performance analysis, design, and iterative decoding," IEEE Trans. Inform. Theory, vol. 44, pp. 909-926, May 1998. Here, the input data is applied to a first convolutional encoder and the output bits of the first encoder, after interleaving, are used as the input bits for a second convolutional encoder. The output bits of the second encoder are then mapped into signal points of a 2D 4-PSK signaling constellation for transmission. The above-mentioned error floor phenomenon is less pronounced for serial-concatenated turbo codes than for parallel-concatenated turbo codes, thereby providing better coding gain at lower error rates. However, these serial-concatenated turbo codes generate more redundant bits than in the parallel case, so that they are less bandwidth-efficient. Moreover, they too require a long interleaver.
Neither the parallel-concatenated, nor the serial-concatenated turbo codes described in the above-discussed prior art references are bandwidth efficient; each of them has a bandwidth efficiency of less than two bits per 2D signal point. More bandwidth-efficient parallel concatenated turbo codes are known, however. See, for example, S. Benedetto, et al, "Bandwidth efficient parallel concatenated coding schemes," Electron. Lett., vol. 31, pp. 2067-2069, 1995, and P. Robertson, et al, "Coded modulation scheme employing turbo codes," Electron. Lett., vol. 31, pp. 1546-1547, 1995. The arrangements disclosed in these references achieve high coding gains at high error rate while featuring an improved bandwidth efficiency of a full 2 bits per 2D signal point by using rate-2/3 trellis codes designed jointly with a 2D 8-PSK signaling constellation rather than the convolutional codes with a 2D 4-PSK constellation used in the Berrou arrangement. However, these latter codes still exhibit the above-mentioned error floor phenomenon and long delays.
The prior art also teaches that another way of achieving increased bandwidth efficiency while achieving the advantages of the turbo code approach is to employ so-called multi-level coding in which the code used in at least one of the levels is a parallel-concatenated turbo code of the kind disclosed by Berrou. (As is well known, a multilevel code is one in which the output bits of different codes are used to select increasingly finer subsets, and ultimately a single signal point, of the signal constellation.) Such a code is disclosed in U. Wachsmann, et al, "Power and bandwidth efficient digital communication using turbo codes in multilevel codes," Euro. Trans. Telecommun., vol. 6, pp. 557-567, September 1995. However, the error floor and delay characteristics of such a multi-level code promise to be no better-and may prove to be worse-than that of the parallel-concatenated turbo code used in a non-multi-level-coding arrangement.
U.S. application Ser. No. 09/451070, filed Nov. 30, 1999, entitled Serial-Concatenated Turbo Codes, is directed to serial-concatenated turbo codes, which were defined therein to mean turbo codes for which at least some of the output bits, including at least one redundant bit, provided by a first, outer encoder are further processed, after interleaving, by a second, inner encoder. Such turbo codes may be of any desired dimensionality, N.gtoreq.1, meaning that the data to be transmitted is represented by an N-tuple, or N-dimensional symbol, whose N coordinates are selected by the output bits of the encoders interdependently. For example, when N is an even integer, an N-dimensional symbol may be conveniently transmitted, during an N-dimensional "symbol interval," as a combination of N/2 2D signal points, wherein each so-called signal space coordinate of the 2D signal point is represented, during a 2D "signaling interval," by the amplitude of an in-phase or quadrature-phase component of a modulated carrier signal. Thus the aforementioned symbol interval is made up of N/2 signaling intervals. For the code where N=2, the symbol interval and the signaling interval are the same.
More specifically, in turbo codes embodying the principles of the invention of U.S application Ser. No. 09/451070, a) the state of each of the inner and outer encoders is advanced only once per symbol interval, and b) all of the data bits, and at least one redundant bit generated by one or both of the encoders for that symbol interval are transmitted together during a single symbol interval, and c) the inner and outer encoders are trellis encoders. This approach advantageously provides turbo codes having a lower delay than prior arrangements and, in addition, affords an advantageous combination of error rate performance, bandwidth efficiency, and decoder complexity not achieved by prior arrangements and exhibiting a less pronounced (or perhaps no) error floor. The inner and outer codes may be of any desired dimensionality.
Arrangements embodying the principles of the invention of U.S application Ser. No. 09/451070 utilize a signal constellation of sufficient size (i.e., number of symbols in the constellation) to accommodate the transmission of the data bits and redundant bits within the aforementioned single symbol interval. Moreover, in preferred embodiments, the turbo code, the constellation, and the mapping between the bits to be transmitted and the constellation symbols are selected in view of one another in such a way that the code complexity and interleaving delay necessary to achieve a given level of error rate performance are less than they would be if the turbo code, constellation and mapping were not selected in view of one another. This is referred to in the art as a "joint design," as more formally defined hereinbelow.
For various reasons, in certain applications it may be desirable to periodically terminate the turbo code. This means that after random input data has been applied to the turbo encoder for some number of symbol intervals, data other than random input bits is thereupon applied to the turbo encoder over a sufficient number of symbol intervals so as to bring each of the encoders to a known state. Random data bits are then again applied to the turbo encoder and the code is thereafter again terminated, and so forth. Terminating a turbo code is desirable because the decoder--which has explicit knowledge of how the code is terminated in the transmitter--can be less complex (measured in processing time and/or memory requirements) than otherwise. Furthermore, it is advantageous to terminate a turbo code (as well as more conventional convolutional and trellis codes) in, for example, packet transmission environments, for reasons discussed, for example, in my United States patent application Ser. No. 09/247704 filed Feb. 9, 1999. Termination of codes may also be advantageous in so-called continuous transmission environments, e.g., voiceband modem applications, as a way of containing the effects of error propagation.